# -*- encoding: utf-8 -*-

"""
------------------------------------------
@File       : min_times_to_unlock.py
@Author     : maixiaochai
@Email      : maixiaochai@outlook.com
@CreatedOn  : 2021/12/7 11:40
------------------------------------------
    解开密码锁的最少次数
    LeetCode.752
    难度中等
"""
from queue import Queue


def plus_one(s, j):
    """
        将 s[j]向上拨动一次
    """
    ch = list(s)

    if ch[j] == '9':
        ch[j] = '0'

    else:
        ch[j] = str(int(ch[j]) + 1)

    return ''.join(ch)


def minus_one(s, j):
    """
        将 s[j]向下拨动一次
    """
    ch = list(s)

    if ch[j] == '0':
        ch[j] = '9'

    else:
        ch[j] = str(int(ch[j]) - 1)

    return ''.join(ch)


def bfs(target):
    """
        BFS框架，打印出所有可能的密码
        这个是从零开始版，不管什么算法不算法，从第一步开始来
    """
    q = Queue()
    q.put('0000')

    while not q.empty():
        size = q.qsize()

        # 将当前队列中的所有节点向周围扩散
        for i in range(size):
            cur = q.get()

            # 判断是否到达终点，这里源码居然用 print ~，是让人肉眼看吗？
            print(cur)

            # 将一个节点的相邻节点加入队列
            for j in range(4):
                up = plus_one(cur, j)
                down = minus_one(cur, j)
                q.put(up)
                q.put(down)

    return


def open_lock(dead_ends, target):
    deads = set(dead_ends)

    # 记录已经穷举过的密码，防止走回头路
    # TODO:这个算法代码有问题，经查源码和本书的相关评论，决定弃坑
    visited = set()

    q = Queue()

    # 从起点开始启动广度优先搜索
    step = 0

    counter = 1

    q.put('0000')
    visited.add('0000')

    while not q.empty():
        sz = q.qsize()

        # 当前队列中所有节点向外扩散
        for _ in range(sz):
            cur = q.get()

            if cur in deads:
                continue

            print(f"NO.{counter}, cur: {cur}")
            counter += 1

            if cur == target:
                return step

            # 将一个节点的未遍历相邻节点加入队列
            for j in range(4):

                up = plus_one(cur, j)
                if up not in deads:
                    q.put(up)
                    visited.add(up)

                down = minus_one(cur, j)
                if down not in deads:
                    q.put(down)
                    visited.add(down)

        step += 1

    return -1


def demo():
    for i in range(4):
        data1 = plus_one('0000', i)
        print(data1)

        data2 = minus_one('0000', i)
        print(data2)


if __name__ == '__main__':
    deads_ = ['9000', '1000']
    target_ = '8000'

    # print(deads_)
    # print(type(deads_))

    # demo()

    data = open_lock(deads_, target_)
    print(data)
